package demo01Array;

/**
 * @Author shenxinyuan
 * @Description //TODO
 * @Date 10:50 2021/7/17
 * @Param
 * @return
 **/
public class BinarySerach {

    //初始化升序数组
    static int[] arr = {2, 5, 8, 9, 45, 120, 120, 160, 1024};


    public static void main(String[] args) {

        int target = 45;

        System.out.println("searchByRecursion(0,arr.length-1,target) = " + searchByRecursion(0, arr.length - 1, target));

        System.out.println("searchByWhile(target) = " + searchByWhile(target));


    }

    //递归 二分查找
    private static int searchByRecursion(int left, int right, int target) {
        left = 0;
        right = arr.length - 1;
        int mid = (right - left) / 2 + left;
        while (left <= right) {
            if (arr[mid] > target) {
                return searchByRecursion(left, mid - 1, target);
            } else if (arr[mid] < target) {
                return searchByRecursion(mid + 1, right, target);
            } else {
                return mid;
            }
        }
        return -1;
    }


    //非递归，二分查找

    private static int searchByWhile(int target) {

        int left = 0;
        int right = arr.length - 1;
        int mid = 0;
        while (left <= right) {
            mid = (right - left) / 2 + left;
            if (arr[mid] > target) {
                right = mid - 1;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}
